package oj.hot100;

public class 回文链表 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public boolean isPalindrome(ListNode head) {
        //拿到中间节点
        ListNode s = endOfFirstHalf(head);
        //从中间节点开始,把后半部分链表反转
        ListNode rightHead = reverseList(s.next);
        ListNode p1 = head;
        ListNode p2 = rightHead;
        boolean result = true;
        while(p2 != null && result) {
            if(p2.val != p1.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        //把后半部分链表反转回来
        s.next = reverseList(rightHead);
        return result;
    }

    //头插法反转链表
    public ListNode reverseList(ListNode head) {
        //没有节点或者只有一个节点
        if(head == null || head.next == null) {
            return head;
        }
        ListNode pre = head,cur = head.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        //头变尾,记得指向null.
        head.next = null;
        return pre;
    }
    private ListNode endOfFirstHalf(ListNode head) {
        ListNode f = head;
        ListNode s = head;
        while(f.next != null && f.next.next != null) {
            f = f.next.next;
            s = s.next;
        }
        return s;
    }
}
